package com.zx._12_算法.数据结构.tree;

/**
 * @version v1.0
 * @Project: knowledge
 * @Title: Trie
 * @Description: 字典树
 * @author: zhangxue
 * @date: 2019年10月22日下午9:12:33
 * @company: 未知
 * @Copyright: Copyright (c) 2015
 */
public class Trie {

    private final int ALPHABET_SIZE = 26;
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        trie.insert("simple");
        trie.insert("app");

        System.out.println("search#app:" + trie.search("app")); // true
        System.out.println("search#apple:" + trie.startsWith("apple"));// true
        System.out.println("search#bcs:" + trie.startsWith("bcs"));//false
        System.out.println("search#ap:" + trie.startsWith("ap"));//false

        System.out.println("startsWith#app:" + trie.startsWith("app"));// true
        System.out.println("startsWith#apple:" + trie.startsWith("apple"));// true
        System.out.println("startsWith#bcs:" + trie.startsWith("bcs"));//false
        System.out.println("startsWith#ap:" + trie.startsWith("ap"));// true


    }

    public void insert(String word) {
        word = word.toLowerCase();//全都转为小写
        TrieNode pointer = this.root;
        char[] charArray = word.toCharArray();
        for (char c : charArray) {
            if (pointer.children[c - 'a'] == null) {
                pointer.children[c - 'a'] = new TrieNode();
            }
            pointer = pointer.children[c - 'a'];
        }
        pointer.isWordOrNot = true;
    }

    public boolean search(String word) {
        word = word.toLowerCase();//全都转为小写
        TrieNode pointer = this.root;
        char[] charArray = word.toCharArray();
        for (char c : charArray) {
            if (pointer.children[c - 'a'] != null) {
                pointer = pointer.children[c - 'a'];
            } else {
                break;
            }
        }
        return pointer.isWordOrNot;
    }

    public boolean startsWith(String prefix) {
        prefix = prefix.toLowerCase();
        char[] charArray = prefix.toCharArray();
        TrieNode pointer = this.root;
        boolean result = true;
        for (char c : charArray) {
            if (pointer.children[c - 'a'] != null) {
                pointer = pointer.children[c - 'a'];
            } else {
                result = false;
                break;
            }
        }

        return result;
    }

    private class TrieNode {

        TrieNode[] children = new TrieNode[ALPHABET_SIZE];
        boolean isWordOrNot = false;
    }

}
